class Solution
{
public:
    int coinChange(vector<int> &coins, int amount)
    {
        vector<int> dp(amount + 1, -1);
        dp[0] = 0;

        function<int(int)> dfs = [&](int target)
        {
            if (dp[target] != -1)
            {
                return dp[target];
            }
            int result = INT_MAX;
            for (int coin : coins)
            {
                if (coin <= target)
                {
                    int c = dfs(target - coin);
                    if (c >= 0)
                    {
                        result = min(result, c + 1);
                    }
                }
            }
            if (result == INT_MAX)
            {
                result = -2;
            }
            return dp[target] = result;
        };
        int ans = dfs(amount);
        return ans >= 0 ? ans : -1;
    }
};